#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn=2e6+7;
const ll inf=1e15;
struct TREE{
	int l,r;
	ll val,tag;
}tree[Maxn<<2],tree1[Maxn<<2];


inline void pushup1(int node){
	tree1[node].val=max(tree1[node<<1].val,tree1[node<<1|1].val);
}
inline void spread(int node,ll kk){
	tree1[node].val=max(tree1[node].val,kk);
	tree1[node].tag=kk;
}
inline void pushdown(int node){
	if(tree1[node].tag==-inf) return ;
	spread(node<<1,tree1[node].tag);
	spread(node<<1|1,tree1[node].tag);
	tree1[node].tag=-inf;
}
void buildtree1(int node,int l,int r){
	tree1[node].l=l;
	tree1[node].r=r;
	tree1[node].tag=-inf;
	if(l==r){
		tree1[node].val=-inf;
		return ;
	}
	int mid=l+r>>1;
	buildtree1(node<<1,l,mid);
	buildtree1(node<<1|1,mid+1,r);
	pushup1(node);
}
void modify1(int node,int l,int r,int k){
	if(tree1[node].l>=l and tree1[node].r<=r){
		spread(node,k);
		return ;
	}
	pushdown(node);
	int mid=tree1[node].l+tree1[node].r>>1;
	if(l<=mid) modify1(node<<1,l,r,k);
	if(r>mid) modify1(node<<1|1,l,r,k);
	pushup1(node);
}
ll query1(int node,int l,int r){
	if(tree1[node].l>=l and tree1[node].r<=r) return tree1[node].val;
	pushdown(node);
	ll ret=-inf;
	int mid=tree1[node].l+tree1[node].r>>1;
	if(l<=mid) ret=max(ret,query1(node<<1,l,r));
	if(r>mid) ret=max(ret,query1(node<<1|1,l,r));
	return ret;
} 

inline void pushup(int node){
	tree[node].val=min(tree[node<<1].val,tree[node<<1|1].val);
}
void buildtree(int node,int l,int r){
	tree[node].l=l;
	tree[node].r=r;
	if(l==r){
		tree[node].val=inf;
		return ;
	}
	int mid=l+r>>1;
	buildtree(node<<1,l,mid);
	buildtree(node<<1|1,mid+1,r);
	pushup(node);
}
void modify(int node,int x,int k){
	if(tree[node].l==tree[node].r){
		tree[node].val=k;
		return ;
	}
	int mid=tree[node].l+tree[node].r>>1;
	if(x<=mid) modify(node<<1,x,k);
	else modify(node<<1|1,x,k);
	pushup(node);
}
ll query(int node,int l,int r){
	if(tree[node].r<l or tree[node].l>r) return inf;
	if(tree[node].l>=l and tree[node].r<=r) return tree[node].val;
	ll ret=inf;
	int mid=tree[node].l+tree[node].r>>1;
	if(l<=mid) ret=min(ret,query(node<<1,l,r));
	if(r>mid) ret=min(ret,query(node<<1|1,l,r));
	return ret;
} 

int n,m;
int a[Maxn];
vector<int>v[Maxn];
int ml[Maxn],ps[Maxn];
ll f[Maxn];

int main(){
	freopen("gonna.in","r",stdin);
	freopen("gonna.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	buildtree(1,0,n);
	buildtree1(1,1,n);
	scanf("%d",&m);
	int L=0,R=0;
	for(int i=1;i<=m;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		L=max(L,l);
		R=max(R,r);
		v[r].emplace_back(l);
		modify1(1,l,r,l);
	}
	
	for(int i=1;i<=n;i++) ps[i]=query1(1,i,i);
	int mx=0;
	for(int i=1;i<=n;i++){
		for(auto j:v[i]) mx=max(mx,j);
		ml[i]=mx;
	}
	modify(1,0,0);
	
	for(int i=1;i<=n;i++){
		cout<<ps[i]<<" "<<endl;
		f[i]=min(query(1,ml[ps[i]-1],ps[i]-1)+a[i],query(1,ps[i],i-1));
//		cout<<i<<" "<<query(1,ml[ps[i]-1],ps[i]-1)+a[i]<<" "<<f[i]<<endl;
		modify(1,i,f[i]);
	}
	ll ans=0;
	for(int i=L;i<=R;i++) ans=max(ans,f[i]);
	cout<<ans;
	

	return 0;
}
/*
5
7 3 4 2 2
3
1 4
2 3
4 5
*/
